package a1sort.a3quicksort;

import java.util.Arrays;
import java.util.Random;

/**
 * @author zhangMr
 * @description
 * 快速排序-参考算法导论第七章
 * 最坏运行时间Θn²
 * 期望运行时间n㏒n
 */
public class QuickSort {
    public static void quickSort(Integer[] data,Integer p,Integer r){
        if(p<r){
            int q=partition(data,p,r);
            quickSort(data,p,q-1);
            quickSort(data,q+1,r);
        }
    }
    public static int partition(Integer[] data,Integer p,Integer r){
        Integer x=data[r];
        int i=p-1;
        for(int j=p;j<r;j++){
            if(data[j]<=x){
                i++;
                Integer temp=data[i];
                data[i]=data[j];
                data[j]=temp;
            }
        }
        Integer temp=data[i+1];
        data[i+1]=x;
        data[r]=temp;
        return i+1;
    }

    public static void main(String[] args) {
        Random random=new Random();
        Integer[]data=new Integer[10];
        for(int i=0;i<10;i++){
            data[i]= random.nextInt(100);
        }
        System.out.println("随机生成的数组"+ Arrays.toString(data));
        quickSort(data,0,data.length-1);
        System.out.println("排序后的数组"+Arrays.toString(data));
    }
}
